﻿/*****************************************************
 * File:            Directed_CPP.cs
 * Description:     Chineese Postman Problem for directed graphs (test model)
 * By:              Ali Khalili (khalili DOT ir AT gmail DOT com)
 * Project:         Automata Learning
 * Namespece		AIDE.Graph
 * Requirements:    
 * Change log:
 *          -15 May 2013:  Initial Deveopment
 * To Do:
 *          -This is not optimized at all!!!!
 * License:
 *****************************************************/

#define DEBUG_GRAPH_VERIFYTRANSITIONTOUR
using System;
using System.Collections.Generic;
using SMLib.Base;
using SMLib.Automata.Base;
//using AIDE.Base;

namespace MBT.GraphAlgorithms
{
    /// <summary>
    /// Chineese Postman Problem for directed graphs. It is usd for transition coverage of graph
    /// (it is somehow rural CPP but not general RCPP, the optional edges here are just the reset ones, i.e. an special edge to initial state)
    /// <remarks>Important note: We assume that:
    /// (i) the graph is connected, i.e. all edges are reachable 
    /// (ii) we can always and in each state reset the system (so, we can make the graph strongly connected, if it is not)
    /// (iii) the graph doesn't have negative cycles
    /// </remarks>
    /// </summary>
    public class Directed_CPP<STATETYPE, TRANSITIONTYPE>
        //where TRANSITIONTYPE : ITransition<STATETYPE>
        //where STATETYPE : IState<TRANSITIONTYPE>
    {
        #region -=[ internal class ]=-
        /// <summary>
        /// Reset transition: This is an special transition to make a model strongly connected
        /// </summary>
        class ResetTransition
             //: ITransition<STATETYPE>
        {
            public ResetTransition(STATETYPE dest)
            {
                this.dest = dest;
            }

            public override string ToString()
            {
                return "Reset";
            }

            STATETYPE dest;
            #region ITransition Members

            public STATETYPE Destination
            {
                get { return dest; }
            }

            #endregion
        }
        #endregion


        /// <summary>
        /// The graph
        /// </summary>
        IDiGraph<STATETYPE, TRANSITIONTYPE> graph;
        ///// <summary>
        ///// optional edge indicator
        ///// </summary>
        //IsOptional optionalityFunc;
        /// <summary>
        /// Assign cost of transitions
        /// </summary>
        TransitionCostAssigner<TRANSITIONTYPE> costAss;
        /// <summary>
        /// Balancing of nodes
        /// </summary>
        int[] delta;
        /// <summary>
        /// Number of nodes in the graph
        /// </summary>
        int N;
        /// <summary>
        /// path[i][j]: shortest path from i and j is pathing from this node
        ///     -infinity: no path found yet
        ///     -1: it is connected directly with an edge
        ///     -2: it is the same node!
        /// </summary>
        int[][] path;
        /// <summary>
        /// Cost[i][j]: minimal cost between edge i and j
        /// </summary>
        int[][] cost;
        /// <summary>
        /// Counts arcs between vertices
        /// </summary>
        int[][] arcs;
        /// <summary>
        /// How frequent each arc should be taken in CPT
        /// [ToDO: we can optimize it, instead of having n*n array, we can have n+e array]
        /// </summary>
        //int[][] freq;

        /// <summary>
        /// Some numbers to be used in verification of the generated tour
        /// </summary>
        int numberOfEdges, numberOfResets, numberOfDuplications;

        /// <summary>
        /// Constructor
        /// </summary>
        /// <param name="graph">the graph</param>
        /// <param name="optionalityFunc">optional edge indicator</param>
        public Directed_CPP(IDiGraph<STATETYPE, TRANSITIONTYPE> graph, TransitionCostAssigner<TRANSITIONTYPE> costAss)
        {
            this.graph = graph;
            //this.optionalityFunc = optionalityFunc;
            this.costAss = costAss;
            numberOfEdges = numberOfResets = numberOfDuplications = 0;
            delta = new int[graph.Size];
            N = graph.Size;


            //freq = NewTwoDimArray<int>(N);
            cost = NewTwoDimArray<int>(N);
            path = NewTwoDimArray<int>(N);
            arcs = NewTwoDimArray<int>(N);
            for (int i = 0; i < N; i++)
                for (int j = 0; j < N; j++)
                {
                    path[i][j] = int.MinValue;
                    if (i == j)
                    {
                        cost[i][j] = 0;
                        path[i][j] = i;//?
                    }
                    else
                    {
                        cost[i][j] = int.MaxValue;
                    }
                }

            //* initial values for the costs
            for (int i = 0; i < N; i++)
            {
            	foreach (TRANSITIONTYPE t in graph.TransitionsOf(graph[i]))
                {
            		int j = graph.IndexOf(graph.DestinationOf(t));
                    cost[i][j] = Math.Min(cost[i][j], CostOfEdge(t));
                    path[i][j] = j;
                    arcs[i][j]++;
                    numberOfEdges++;
                }
            }
        }



        /// <summary>
        /// Create a new two dimentional array ([size][size])
        /// </summary>
        /// <typeparam name="T">of type T</typeparam>
        /// <param name="arr"></param>
        /// <param name="size">size of array</param>
        /// <returns></returns>
        T[][] NewTwoDimArray<T>(int size)
        {
            T[][] arr;
            arr = new T[size][];
            for (int i = 0; i < size; i++)
                arr[i] = new T[N];
            return arr;
        }

        /// <summary>
        /// Post processing. After finishing the process, remove all resets that added
        /// </summary>
        void RemoveResets()
        {
            foreach (STATETYPE st in graph.GetStates())
            {
            	if (graph.TransitionsOf(st).Count > 0 &&
            	    (graph.TransitionsOf(st)[graph.TransitionsOf(st).Count - 1] is ResetTransition || graph.TransitionsOf(st)[graph.TransitionsOf(st).Count - 1] == null))
                {
            		graph.TransitionsOf(st).RemoveAt(graph.TransitionsOf(st).Count - 1);
                }
            }
        }

        /// <summary>
        /// Cost of edge
        /// </summary>
        /// <param name="edge"></param>
        /// <returns></returns>
        int CostOfEdge(TRANSITIONTYPE edge)
        {
            if (edge is ResetTransition || edge == null)
                return 1;
            else
            {
                if (costAss == null) return 1;
                return costAss(edge);
            }
        }

        /// <summary>
        /// This converts the problem from rural CPP into usual CPP by 
        /// selecting the minimal set of optional edges on the graph
        /// to make it strongly connected; (offcourse it is not OPTIMIZED!)
        /// </summary>
        void MakeItStronglyConnected()
        {
            List<int> ZeroNotReachable = new List<int>();
            for (int iii = 0; iii < graph.Size; iii++)
            {
                if (cost[iii][0] == int.MaxValue)//(path[i][0] == -1)
                {
                    ZeroNotReachable.Add(iii);
                }
            }

            //[ToDo1: not add all!]
            for (int iii = 0; iii < ZeroNotReachable.Count; iii++)
            {
                if (iii > 0)
                {
                    for (int y = iii; y < ZeroNotReachable.Count; y++)
                    {
                        //* Ops! it was wrong!!!
                        if (cost[ZeroNotReachable[y]][0] != int.MaxValue)
                        {
                            ZeroNotReachable.RemoveAt(y);
                            y--;
                        }
                    }
                    if (iii >= ZeroNotReachable.Count)
                        break;
                }
                TRANSITIONTYPE tr = default(TRANSITIONTYPE);// new ResetTransition<STATETYPE>(graph[0]);

                graph.TransitionsOf(graph[ZeroNotReachable[iii]]).Add(tr);
                cost[ZeroNotReachable[iii]][0] = CostOfEdge(tr);
                path[ZeroNotReachable[iii]][0] = 0;
                numberOfResets++;

                int k = 0;
                for (int i = 0; i < N; i++)
                {
                    if (cost[i][k] != int.MaxValue)
                    {
                        for (int j = 0; j < N; j++)
                        {
                            if (cost[i][k] != int.MaxValue
                                && (cost[i][j] > cost[i][k] + cost[k][j]))
                            {
                                path[i][j] = path[i][k];
                                cost[i][j] = cost[i][k] + cost[k][j];
                                if (i == j && cost[i][j] < 0) return; //stop on negative cycle
                            }
                        }
                    }
                }
                k = ZeroNotReachable[iii];
                for (int i = 0; i < N; i++)
                {
                    if (cost[i][k] != int.MaxValue)
                    {
                        for (int j = 0; j < N; j++)
                        {
                            if (cost[i][k] != int.MaxValue
                                && (cost[i][j] > cost[i][k] + cost[k][j]))
                            {
                                path[i][j] = path[i][k];
                                cost[i][j] = cost[i][k] + cost[k][j];
                                if (i == j && cost[i][j] < 0) return; //stop on negative cycle
                            }
                        }
                    }
                }
            }
        }

        /// <summary>
        /// Compute balance of each node. Result is stored in "delta" array as a negative/positive integer number
        /// </summary>
        void ComputeBalanceOfNodes()
        {
            for (int i = 0; i < N; i++)
            {
                //* outgoing: positive degree
                delta[i] += graph.TransitionsOf(graph[i]).Count;

                foreach (TRANSITIONTYPE t in graph.TransitionsOf(graph[i]))
                {
                    if (t == null)
                    {
                        //* t is reset!
                        delta[0]--;
                        //Console.WriteLine("...!");
                        break;
                    }

                    //* incomming: negative degree
                    for (int j = 0; j < N; j++)
                    {

                    	if (object.ReferenceEquals(graph.DestinationOf(t), graph[j]))
                        {
                            delta[j]--;
                            break;
                        }
                    }
                }
            }
        }




        /// <summary>
        ///  Floyd-Warshall algorithm: Find shortest path between each pairs of nodes
        /// <assumptions>
        /// The graph does't have negative cycles 
        /// </assumptions>
        /// </summary>
        void LeastCostPaths()
        {
            for (int k = 0; k < N; k++)
            {
                for (int i = 0; i < N; i++)
                {
                    if (i != k && cost[i][k] != int.MaxValue)
                    {
                        for (int j = 0; j < N; j++)
                        {
                            if (j == i || j == k)
                                continue;

                            if (cost[k][j] != int.MaxValue
                                && (cost[i][j] > cost[i][k] + cost[k][j]))
                            {
                                path[i][j] = path[i][k];
                                cost[i][j] = cost[i][k] + cost[k][j];
                                if (i == j && cost[i][j] < 0) return; //stop on negative cycle
                            }
                        }
                    }
                }
            }
        }




        /// <summary>
        /// Solve the CPP Problem 
        /// </summary>
        void SolveProblem()
        {
            //* find the shortest path between each of two nodes
            LeastCostPaths();
            //* Add reset arcs to make the graph strongly connected
            MakeItStronglyConnected();
            //* Compute balance of node 
            ComputeBalanceOfNodes();
            //AIDE.Automata.Utils.AutomataUtils.DrawAutomata(this.graph);
            //* and then find nodes with non-zero balance
            //FindUnbalancedNodes();
            //* find one possible solution
            //FindFeasible();
            //* then improve the solution as much as possible
            //* while (improvements()) ;
        }


        int DestinationOf(TRANSITIONTYPE t)
        {
            return (t == null ? 0 : graph.IndexOf(graph.DestinationOf(t)));
        }

        /// <summary>
        /// Find the shortest path between two nodes
        /// </summary>
        /// <param name="srcInd">source node</param>
        /// <param name="dstInd">target node</param>
        /// <returns>path</returns>
        List<TRANSITIONTYPE> PathBetween(int srcInd, int dstInd)
        {
            List<TRANSITIONTYPE> myPath = new List<TRANSITIONTYPE>();
            int currInd = srcInd;
            while (currInd != dstInd)
            {
                int nxtInd = path[currInd][dstInd];
                int minVal = int.MaxValue, minIndex = -1;
                for (int i = 0; i < graph.TransitionsOf(graph[currInd]).Count; i++)
                {
                    //if (graph.IndexOf(graph[currInd].Transitions[i].Destination) == nxtInd &&
                    //    CostOfEdge(graph[currInd].Transitions[i]) < minVal)
                    if (DestinationOf(graph.TransitionsOf(graph[currInd])[i]) == nxtInd &&
                        CostOfEdge(graph.TransitionsOf(graph[currInd])[i]) < minVal)
                    {
                        minIndex = i;
                        minVal = CostOfEdge(graph.TransitionsOf(graph[currInd])[i]);
                    }
                }
                myPath.Add(graph.TransitionsOf(graph[currInd])[minIndex]);
                numberOfDuplications++;
                currInd = nxtInd;
            }

            return myPath;
        }

        /// <summary>
        /// It is not very optimized!
        /// <remarks>Finding a transition tour of an Euilerian Graph based on Hierholzer's algorithm</remarks>
        /// </summary>
        public List<TRANSITIONTYPE> ComputeTransitionTour()
        {
            SolveProblem();

            #region This part is the optimization problem
            //* Hint: we know that number of positive degrees and number of negative degrees are equal
            int deg = 0;
            for (int i = 0; i < N; i++)
                if (delta[i] > 0) deg += delta[i];

            int[] neg = new int[deg];
            int[] pos = new int[deg];
            int[] way = new int[deg];


            int nn = 0, pp = 0;
            for (int i = 0; i < N; i++) //initialise sets
                if (delta[i] < 0)
                {
                    for (int y = 0; y > delta[i]; y--)
                        neg[nn++] = i;
                }
                else if (delta[i] > 0)
                {
                    for (int y = 0; y < delta[i]; y++)
                        pos[pp++] = i;
                }

            //* now, find one solution for augmenting the graph to make it Eulerian
            for (int i = 0; i < deg; i++)
            {
                int minIndex = -1;
                int minCost = int.MaxValue;

                for (int j = 0; j < deg; j++)
                {
                    if (pos[j] != -1 && cost[neg[i]][pos[j]] < minCost)
                    {
                        minIndex = j;
                        minCost = cost[neg[i]][pos[j]];
                    }
                }
                way[i] = pos[minIndex];
                pos[minIndex] = -1;
            }
            #endregion

            List<TRANSITIONTYPE> transitionTour = new List<TRANSITIONTYPE>();

            //* note: here we can use the pos (not used anymore)
            int[] numberOfTraversedEdges = new int[N];
            //* now, traverse the graph!

            STATETYPE currentState = graph[0];
            int currentIndex = 0;

            while (true)
            {
            	if (graph.TransitionsOf(currentState).Count > numberOfTraversedEdges[currentIndex])
                {
                    //* select from non-traversed edges
                    TRANSITIONTYPE tr = (graph.TransitionsOf(currentState)[numberOfTraversedEdges[currentIndex]]);
                    numberOfTraversedEdges[currentIndex]++;
                    transitionTour.Add(tr);
                    currentState = (tr == null) ? graph[0] : graph.DestinationOf(tr);
                    currentIndex = graph.IndexOf(currentState);
                }
                else
                {
                    //* find a virtual edge (shortest path)
                    if (delta[currentIndex] < 0 &&
                        graph.TransitionsOf(currentState).Count - delta[currentIndex] > numberOfTraversedEdges[currentIndex])
                    {
                        int destIndex = -1;
                        //*find shortest path destination!
                        for (int y = 0; y < neg.Length; y++)
                        {
                            if (neg[y] == currentIndex)
                            {
                                destIndex = way[y];
                                neg[y] = -1;
                                break;
                            }
                        }
                        //* find shortest path from currIndex to destIndex
                        transitionTour.AddRange(PathBetween(currentIndex, destIndex));
                        numberOfTraversedEdges[currentIndex]++;
                        //* and now, continue!
                        currentState = graph[destIndex];
                        currentIndex = destIndex;
                    }
                    else
                        //* no!
                        break;
                }
            }

            //VerifyTour(transitionTour);

            //* now find not traversed edges!
            while (true)
            {
                int indexOfNT = -1;
                for (int y = 0; y < N; y++)
                {
                	if (numberOfTraversedEdges[y] < graph.TransitionsOf(graph[y]).Count)
                    {
                        indexOfNT = y;
                        break;
                    }
                }
                //* check if all graph is traversed?
                if (indexOfNT == -1)
                    break;

                currentState = graph[indexOfNT];
                currentIndex = indexOfNT;
                int firstNodeIndex = currentIndex;

                List<TRANSITIONTYPE> route = new List<TRANSITIONTYPE>();
                while (true)
                {
                	if (graph.TransitionsOf(currentState).Count > numberOfTraversedEdges[currentIndex])
                    {
                        //* select from non-traversed edges
                        TRANSITIONTYPE tr = (graph.TransitionsOf(currentState)[numberOfTraversedEdges[currentIndex]]);
                        numberOfTraversedEdges[currentIndex]++;
                        route.Add(tr);
                        currentState = graph.DestinationOf(tr);
                        currentIndex = graph.IndexOf(currentState);
                    }
                    else
                    {
                        //* find a virtual edge (shortest path)
                        if (delta[currentIndex] < 0 &&
                            graph.TransitionsOf(currentState).Count - delta[currentIndex] > numberOfTraversedEdges[currentIndex])
                        {
                            int destIndex = -1;
                            //*find shortest path destination!
                            for (int y = 0; y < neg.Length; y++)
                            {
                                if (neg[y] == currentIndex)
                                {
                                    destIndex = way[y];
                                    neg[y] = -1;
                                    break;
                                }
                            }
                            //* find shortest path from currIndex to destIndex
                            route.AddRange(PathBetween(currentIndex, destIndex));

                            numberOfTraversedEdges[currentIndex]++;

                            //* and now, continue!
                            currentState = graph[destIndex];
                            currentIndex = destIndex;
                        }
                        else
                        {
                            for (int y = 0; y < transitionTour.Count; y++)
                            {
                            	if (graph.IndexOf(graph.DestinationOf(transitionTour[y])) == currentIndex)
                                {
                                    transitionTour.InsertRange(y + 1, route);
                                    break;
                                }
                            }
                            if (currentIndex != firstNodeIndex)
                                throw new Exception("Error!");
                            //* no!
                            break;
                        }
                    }
                }
            }
#if DEBUG_GRAPH_VERIFYTRANSITIONTOUR
            VerifyTour(transitionTour);
#endif
            //Console.WriteLine("Lenght of tour: " + transitionTour.Count + " and it should be " +
            //    (numberOfDuplications + numberOfEdges + numberOfResets).ToString() + " (i.e. " + numberOfEdges + "+" + numberOfResets + "+" + numberOfDuplications + ")");
            //LearningLog.LogEvent(("Lenght of tour: " + transitionTour.Count + " and it should be " +
            //                                            (numberOfDuplications + numberOfEdges + numberOfResets).ToString() + " (i.e. " + numberOfEdges + "+" + numberOfResets + "+" + numberOfDuplications + ")"));
            RemoveResets();


            return transitionTour;
        }

        private void VerifyTour(List<TRANSITIONTYPE> tour)
        {
            STATETYPE currState = graph[0];
            for (int i = 0; i < tour.Count; i++)
            {
                bool found = false;
                if (tour[i] == null)
                {
                    currState = graph[0];
                    //Console.Write("RESET ");
                    continue;
                }
                for (int j = 0; j < graph.TransitionsOf(currState).Count; j++)
                {
                	if (object.ReferenceEquals(graph.TransitionsOf(currState)[j], tour[i]))
                    {
                        found = true;
                        currState = graph.DestinationOf(tour[i]);
                        //Console.Write(tour[i] + " ");
                        break;
                    }
                }
                if (!found)
                    throw new Exception("The tour doesn't match with the graph!");
            }
        }

        #region OPTIMIZATION PROBLEM
        ///// <summary>
        ///// Find nodes with positive or negative balance. Results are stored in "neg" and "pos" arrays
        ///// </summary>
        //void FindUnbalancedNodes()
        //{
        //    int nn = 0, np = 0;//number of vertices of negative/positive delta
        //    for (int i = 0; i < N; i++)
        //        if (delta[i] < 0) nn++;
        //        else if (delta[i] > 0) np++;
        //    neg = new int[nn];
        //    pos = new int[np];
        //    nn = np = 0;
        //    for (int i = 0; i < N; i++) //initialise sets
        //        if (delta[i] < 0) neg[nn++] = i;
        //        else if (delta[i] > 0) pos[np++] = i;
        //}

        ///// <summary>
        ///// Solve the optimisation problem
        ///// <remarks>
        ///// Several other approaches exist (including integer programing, matching, ...)
        ///// Cycle canceling [7] can reuse the shortest path results already found, AND we use it because
        ///// it is concise. Cycle canceling starts with an approximate solution, then iteratively improves
        ///// it. Here, the greedy method is used to establish an initial feasible solution: when the method
        ///// terminates, the variable f satisfies the constraints but φ may not yet be optimal.</remarks>
        ///// </summary>
        //void FindFeasible()
        //{
        //    for (int u = 0; u < neg.Length; u++)
        //    {
        //        int i = neg[u];
        //        for (int v = 0; v < pos.Length; v++)
        //        {
        //            int j = pos[v];

        //            freq[i][j] = -delta[i] < delta[j] ? -delta[i] : delta[j];
        //            delta[i] += freq[i][j];
        //            delta[j] -= freq[i][j];
        //        }
        //    }
        //}

        //const int NONE = -1;

        ///// <summary>
        ///// find a path between unbalanced vertices
        ///// </summary>
        ///// <param name="from"></param>
        ///// <param name="f"></param>
        ///// <returns></returns>
        //int FindPath(int from, int[][] f)
        //{
        //    for (int i = 0; i < N; i++)
        //        if (f[from][i] > 0) return i;
        //    return NONE;
        //}

        ///// <summary>
        ///// 
        ///// </summary>
        ///// <returns></returns>
        //public List<ITransition> ComputeTransitionTour()
        //{
        //    List<ITransition> transitionTour = new List<ITransition>();
        //    int v = 0;
        //    while (true)
        //    {
        //        int u = v;
        //        if ((v = FindPath(u, freq)) != NONE)
        //        {
        //            freq[u][v]--; //remove path
        //            for (int p; u != v; u = p)//break down path into its arcs
        //            {
        //                p = path[u][v];
        //                //transitionTour.Add(new NDGraphTraversalStep<string, int>(cheapestLabel[u][p], p, false));
        //                Console.WriteLine("Take arc from " + u + " to " + p);
        //            }
        //        }
        //        else
        //        {
        //            int bridgeVertex = path[u][0];
        //            if (arcs[u][bridgeVertex] == 0)
        //                break; //finished if bridge already used
        //            v = bridgeVertex;
        //            for (int i = 0; i < N; i++)//find an unused arc, using bridge last
        //                if (i != bridgeVertex && arcs[u][i] > 0)
        //                {
        //                    v = i;
        //                    break;
        //                }
        //            arcs[u][v]--; //decrement count of parallel arcs
        //            //transitionTour.Add(new NDGraphTraversalStep<string, int>(label[u][v][(arcs[u][v])], v, false));
        //            Console.WriteLine("Take arc from " + u + " to " + v); //use each arc label in turn
        //        }
        //    }
        //    return transitionTour;
        //}
        #endregion
    }
}
